package thread;
/*
 * @Author 罗
 * @date 2020/10/8 - 3:20 下午
 */

import Sort_06.MergeSorting_07;
import pojo.Person;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.concurrent.*;
import java.util.stream.Collectors;

/**
 * 多线程分支合并算法
 */
public class ForkJoinSort {

    private static int threadNum = Runtime.getRuntime().availableProcessors();


    public static void main(String[] args) throws ExecutionException, InterruptedException {


        List<Person> collect = Arrays.asList(8, 4, 5, 7, 1, 3, 6, 2).stream().map(i -> {
            Person person = new Person();
            person.setPrice(i);
            return person;
        }).collect(Collectors.toList());

        forkTask(collect, 0, collect.size()-1, new ArrayList<>(collect.size()), (p1, p2) -> {
            return p1.getPrice() - p2.getPrice();
        });


        collect.forEach(System.out::println);
    }


    /**
     * 分配线程
     */
    private static <T> void allowThread(List<T> list, Comparator<T> comparator) throws ExecutionException, InterruptedException {

        ForkJoinPool forkJoinPool = new ForkJoinPool(threadNum);

        SortForkJoinTask sortForkJoinTask = new SortForkJoinTask(0, list.size() - 1, comparator, list);


        ForkJoinTask joinTask = forkJoinPool.submit(sortForkJoinTask);

        Object o = joinTask.get();

        forkJoinPool.shutdown();

    }

    static class SortForkJoinTask<T> extends RecursiveTask<List<T>> {

        private Integer leftIndex;

        private Integer rightIndex;

        private List<T> list;

        private Integer result;


        private Comparator<T> comparator;

        public SortForkJoinTask(Integer leftIndex, Integer rightIndex, Comparator<T> comparator, List<T> list) {
            this.leftIndex = leftIndex;
            this.rightIndex = rightIndex;
            this.comparator = comparator;
            this.list = list;
            this.result = 0;

        }

        //@lombok.SneakyThrows
        @Override
        protected List<T> compute() {

            if ((rightIndex - leftIndex) < list.size() / threadNum) {

                forkTask(list, leftIndex, rightIndex, new ArrayList<>(rightIndex - leftIndex), comparator);

            } else {
                int middle = rightIndex - leftIndex;

                SortForkJoinTask task1 = new SortForkJoinTask(leftIndex, rightIndex, comparator, list);

                SortForkJoinTask task2 = new SortForkJoinTask(leftIndex, rightIndex, comparator, list);

                task1.fork();

                task2.fork();

                task1.join();

                task2.join();

                //result = task1.get()+task2.get();

            }

            return null;
        }
    }

    /**
     * 分
     */
    private static <T> void forkTask(List<T> list, int left, int right, List<T> temp, Comparator<T> comparator) {
        if (left < right) {
            int middle = (right + left) / 2;

            forkTask(list, left, middle, temp, comparator);

            forkTask(list, middle + 1, right, temp, comparator);

            joinTask(list, left, middle, right, temp, comparator);
        }
    }

    /***
     * 治
     *
     * @param list
     * @param left
     * @param middle 左边数组的最后一个元素，即 middle+1 就是右边数组的开始
     * @param right
     * @param temp
     * @param comparator
     * @param <T>
     */
    private static <T> void joinTask(List<T> list, int left, int middle, int right, List<T> temp, Comparator<T> comparator) {
        int leftIndex = left;
        int rightIndex = middle + 1;

        // 指向temp的当前索引
        int currentIndex = 0;

        while (leftIndex <= middle && rightIndex <= right) {

            if (comparator.compare(list.get(leftIndex), list.get(rightIndex)) > 0) {

                temp.add(currentIndex, list.get(rightIndex));

                rightIndex++;
            } else {

                temp.add(currentIndex, list.get(leftIndex));
                leftIndex++;
            }
            currentIndex++;

        }

        while (leftIndex <= middle) {
            temp.add(currentIndex, list.get(leftIndex));
            leftIndex++;
            currentIndex++;
        }

        while (rightIndex <= right) {
            temp.add(currentIndex, list.get(rightIndex));
            rightIndex++;
            currentIndex++;
        }

        currentIndex = 0;

        for (int i = left; i <= right; i++, currentIndex++) {
            list.set(i, temp.get(currentIndex));
        }

    }

}
